1. Field of the Invention
The present invention relates to improvements in a variable-length decoding apparatus, and more particularly to a variable-length decoding apparatus reduced in capacity of a look-up table by storing a large number of decoded data with high storage density.
2. Description of the Prior Art
Variable-length decoding is very effective in a reduction in storage density and therefore often used for reproduction of compressed image data with the use of any of a variety of algorithms in recent years. According to the variable-length decoding, the more frequently occurring data out of a variety of types of data is converted into the shorter-length code-data, thus reducing the total bit amount in which all the bits of a large number of data are totalled.
The following description will discuss a conventional variable-length decoding apparatus.
FIG. 9 is a block diagram of a conventional variable-length decoding apparatus. Shown in FIG. 9 are a barrel shifter 31, a pointer 32 for the barrel shifter 31, an external interface 33 into which a bit string containing a plurality of codes in a continuous manner is externally entered, a look-up table 34, and a data processing device 35 for processing a decoded data. As shown in FIG. 9, each data format in the look-up table 34 comprises the number of bits (code length) of a code and a decoded data.
A bit string entered through the external interface 33, is entered into the barrel shifter 31. The barrel shifter 31 supplies, out of the bit string thus entered, a bit string having bits in predetermined number (more specifically, a bit string having the code length of the variable-length code having the maximum code length). The bit string thus supplied, serves as an address value for the look-up table 34, and the decoded data stored at this address value is taken out from the look-up table 34. This decoded data is entered into the data processing device 35, which executes a decoded-data processing and other processing than the decoded-data processing. Also, with the bit string from the barrel shifter 31 serving as an address, the look-up table 34 supplies a signal representing the code length of a code subjected to decoding. This code-length signal is entered into the pointer 32. Upon reception of an instruction from the pointer 32, the barrel shifter 31 shifts the bit string by the code length represented by the code-length signal. This results in exclusion of the decoded code, and the next code is positioned at the head of a bit string having bits in predetermined number which is to be supplied at the next time from the barrel shifter 31.
Recently, it is desired to execute a processing on image data or the like using high frequency to increase the processing speed. In order to shorten the time required for reading a data from the look-up table, it is proposed to dispose, within a chip, a look-up table forming memory, instead of external attachment thereof.
In the arrangement of prior art, however, the look-up table is large in hardware size. This increases the memory in size, resulting in a failure to dispose the memory within the chip for faster processing.
The following description will discuss in detail the defect that the look-up table of prior art is large in hardware size.
For example, when the maximum code length of variable-length codes is 10 bits, there is required a look-up table of capacity as large as 2.sup.10 words. However, the barrel shifter always supplies a bit string having bits in predetermined number (e.g., 10 bits), which is entered into the look-up table. Accordingly, as shown in FIG. 6, for example as to the code [0010] of which code length is [4] and the code [0011] approximate thereto, it is required to store the decoded data for the code [0010] in the table areas in the look-up table between the 10-bit address [0010xxxxxx] (in which [xxxxxx] refers to an arbitrary bit string having six bits following on ([0010]) and the 10-bit address [0011000000]. Accordingly, the look-up table of prior art is low in the storage density of a large number of decoded data. As a result, when the number of the types of variable-length codes is large to lengthen the code length of the variable-length codes, the look-up table is further increased in storage capacity. This disadvantageously increases the look-up table in hardware size.